package 编辑距离;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/20 11:26
 * @description:
 */
public class Solution2 {
    public int minDistance(String word1, String word2) {
        // 二维动态规划：
        // ① dp数组及其下标含义：dp[i][j]表示word1中以下标 j-1 结尾的子串，word2中以下标 j-1 结尾的子串，子串相等的最小操作数
        // ② 状态转移方程：if(wrod1[j-1] == word2[i-1]) dp[i][j] = dp[i-1][j-1]
        //              else dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
        // ③ dp数组的初始化：当i=0时，可以理解为需要删除word1中的每一个字符: dp[0][j] = j;
        //                  当j=0时，可以理解为需要插入word2中的每一个字符：dp[i][0] = i;
        // ④ 遍历方向：从状态转移方程不难看出，是从左上角到右下角的
        // ⑤ 举例推导dp数组：输入：word1 = "horse", word2 = "ros"
        //                index:    0   r   o   s
        //                   0      0   1   2   3
        //                   h      1   1   2   3
        //                   o      2   2   1   2
        //                   r      3   2   2   2
        //                   s      4   3   3   2
        //                   e      5   4   4   3


        int word1Len = word1.length();
        int word2Len = word2.length();

        int[] dp = new int[word2Len + 1];
        // init dp
        for (int i = 0; i <= word2Len; i++) {
            dp[i] = i;
        }
        System.out.println(Arrays.toString(dp));
        // Traversal word1 by row
        for (int i = 1; i <= word1Len; i++) {
            // Traversal word2 by cloumn
            int pre = dp[0]; // record value of dp[i-1]j-1]
            dp[0] = i;
            for (int j = 1; j <= word2Len; j++) {
                int cur = dp[j]; // record next value of dp[i-1][j-1]
                if (word2.charAt(j - 1) == word1.charAt(i - 1)) {
                    dp[j] = pre;
                } else {
                    // 找操作最小，依次是：增 dp[j - 1]，删 dp[j]，替换 pre
                    dp[j] = 1 + Math.min(dp[j - 1], Math.min(dp[j], pre));
                }
                pre = cur; // renew dp[i-1[j-1]
            }
            System.out.println(Arrays.toString(dp));
        }

        return dp[word2Len];
    }
}
